Intersection of Two Arrays

LeetCode 349 | Difficulty: Easy

Easy

Problem Description

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]
Explanation: [4,9] is also accepted.

Constraints:

- `1 <= nums1.length, nums2.length <= 1000`

- `0 <= nums1[i], nums2[i] <= 1000`

Topics: Array, Hash Table, Two Pointers, Binary Search, Sorting

---

Approach

Two Pointers

Use two pointers to traverse the array, reducing the search space at each step. This avoids the need for nested loops, bringing complexity from O(n²) to O(n) or O(n log n) if sorting is involved.

When to use

Array is sorted or can be sorted, and you need to find pairs/triplets that satisfy a condition.

Binary Search

Binary search reduces the search space by half at each step. The key insight is identifying the monotonic property — what condition lets you decide to go left or right?

When to use

Sorted array, or searching for a value in a monotonic function/space.

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

---

Solutions

Solution 1: C# (Best: 128 ms)

Metric	Value
Runtime	128 ms
Memory	41.4 MB
Date	2021-11-12

Solution

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
    
    if(nums1.Length == 0 || nums2.Length == 0) 
    {
        return new int[0];
    }
    
    Array.Sort(nums1);
    Array.Sort(nums2);
    HashSet<int> result = new HashSet<int>();
        
    int m = nums1.Length;
    int n  = nums2.Length;
    int i=0, j=0;
    
    while(i<m && j<n)
    {
        if(nums1[i] == nums2[j])
        {
            result.Add(nums1[i]);
            i++;
            j++;

        }
        else if(nums1[i] < nums2[j])
        {
            i++;
        }
        else
        {
            j++;
        }
    }
    
    return result.Count !=0 ? result.ToArray() : new int[0];
    }
}

📜 2 more C# submission(s)

Submission (2018-04-17) — 304 ms, N/A

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        return nums1.Intersect(nums2).Distinct().ToArray();
    }
}

Submission (2018-04-17) — 316 ms, N/A

public class Solution {
    public int[] Intersection(int[] nums1, int[] nums2) {
        var nums = nums1.ToList();
    List<int> result = new List<int>();
    for (int i = 0; i < nums2.Length; i++)
    {
        if(nums.Contains(nums2[i]))
        result.Add(nums2[i]);
    }
    return result.Distinct().ToArray();
    }
}

---

Complexity Analysis

Approach	Time	Space
Two Pointers	$O(n)$	$O(1)$
Binary Search	$O(log n)$	$O(1)$
Sort + Process	$O(n log n)$	$O(1) to O(n)$
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Start by clarifying edge cases: empty input, single element, all duplicates.
• Ask: "Can I sort the array?" — Sorting often enables two-pointer techniques.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Precisely define what the left and right boundaries represent, and the loop invariant.